O Problema

Esse notebook introduz conceitos do algoritmo de Árvore de Decisão (AD), para ilustrações do fato, usarei o dataset Iris.

# estabelecendo o ambiente
suppressMessages({
        library(tidyverse)
        library(magrittr)
        library(knitr)
        library(GGally)
        library(rpart)
        library(rattle)
        library(rpart.utils)
        })  
setwd("~/Dropbox/kaggle/iris-species/")  
opts_chunk$set(cache=TRUE)  
data(iris)
iris %<>%  as_tibble()

O dataset Íris contém medidas de comprimento e largura da pétala e da sépala de três espécies de íris:

Versicolor

 

Setosa

 

Virgínica

 

Estrutura da flor:

O dataset contém 150 amostras, 50 de cada espécie.

iris %>%  head() %>% print()

A missão

Conhecer o algoritmo de Árvore de Decisão e criar um modelo possível de prever a espécie de íris a partir das medidas da pétala e sépala.

Antes da modelagem e análise em geral, o primeiro passo é dividir o conjunto em dados de treinamento e de teste. Para não criarmos um bias que influencie nas predições feitas sobre o conjunto de teste.

set.seed(654)
train_idx <- sample(nrow(iris), .75*nrow(iris))
train <- iris %>% slice(train_idx)
test <- iris %>% slice(-train_idx)

No dataset constam 4 preditores, é interessante checar o nível de correlação deles, e ou separação no plano que delineie as classes que queremos classificar.

train %>%
        ggpairs(aes(colour=Species), columns=1:4, lower="blank", diag="blank", 
                  upper=list(continuous="points")) + theme_bw() 

 plot: [1,1] [=====-------------------------------------------------------------------------]  6% est: 0s 
 plot: [1,2] [==========--------------------------------------------------------------------] 12% est: 1s 
 plot: [1,3] [===============---------------------------------------------------------------] 19% est: 3s 
 plot: [1,4] [====================----------------------------------------------------------] 25% est: 4s 
 plot: [2,1] [========================------------------------------------------------------] 31% est: 3s 
 plot: [2,2] [=============================-------------------------------------------------] 38% est: 2s 
 plot: [2,3] [==================================--------------------------------------------] 44% est: 2s 
 plot: [2,4] [=======================================---------------------------------------] 50% est: 2s 
 plot: [3,1] [============================================----------------------------------] 56% est: 1s 
 plot: [3,2] [=================================================-----------------------------] 62% est: 1s 
 plot: [3,3] [======================================================------------------------] 69% est: 1s 
 plot: [3,4] [==========================================================--------------------] 75% est: 1s 
 plot: [4,1] [===============================================================---------------] 81% est: 0s 
 plot: [4,2] [====================================================================----------] 88% est: 0s 
 plot: [4,3] [=========================================================================-----] 94% est: 0s 
 plot: [4,4] [==============================================================================]100% est: 0s 
                                                                                                          

Algumas variáveis apresentam uma correlação bem forte, como Petal.Length e Petal.Width, e as regiões de tamanho das pétalas tem uma apresentam uma diferenciação bem clara das classes.

 


Aprendizado de Máquina

Dentro do espaço Preditor \(\Large{X}\) encontrar a melhor separação de sub-espaços que designem cada classe.

\[ \Large{\mathcal{F}} : X \rightarrow Y \]


Árvore de Decisão


Definições

Olhando um exemplo genérico de AD para o caso íris na figura abaixo, nesse exemplo só constam 2 preditores.

  • Abordagem Top-Down -> imagina a árvore invertida, o cume do grafo é a Raiz.
  • Os nós internos são Ramais.
  • Os nós terminais são Folhas, cada qual designa uma classe e representam micros-regiões oriundas da divisão do espaço de Preditores.
tree.fit <- rpart("Species ~ Petal.Length + Petal.Width", train, control=rpart.control(cp=0, minbucket=1))
fancyRpartPlot(tree.fit, sub="")


Regiões de decisão

limiares <- rpart.subrules.table(tree.fit) %>% 
                as_tibble() %>%
                select(Variable, Less) %>% 
                filter(!is.na(Less)) %>% 
                mutate(Less=as.numeric(as.character(Less)))
                
limiares_pl <- limiares %>% filter(Variable=="Petal.Length") %>%  .$Less           
limiares_pw <- limiares %>% filter(Variable=="Petal.Width") %>%  .$Less           
x_axis <- train$Petal.Length %>% range()
y_axis <- train$Petal.Width %>% range()
n_points <- train %>% nrow()
            
train %>% ggplot(aes(x=Petal.Length, y=Petal.Width, colour=Species)) +
            geom_point() + theme_bw() + scale_x_continuous(breaks=seq(10,1)) +
            geom_line(aes(x=rep(limiares_pl[1], n_points), y=seq(y_axis[1], y_axis[2], length.out=n_points)), colour="black") + 
            geom_line(aes(x=seq(limiares_pl[2], x_axis[2], length.out=n_points), y=rep(limiares_pw[1], n_points)), colour="black") +
            geom_line(aes(x=rep(limiares_pl[2], n_points), y=seq(y_axis[1], y_axis[2], length.out=n_points)), colour="black") +
            geom_line(aes(x=seq(limiares_pl[2], x_axis[2], length.out=n_points), y=rep(limiares_pw[1], n_points)), colour="black") +
            geom_line(aes(x=rep(limiares_pl[3], n_points), y=seq(y_axis[1], limiares_pw[1], length.out=n_points)), colour="black") +
            geom_line(aes(x=seq(limiares_pl[3], x_axis[2], length.out=n_points), y=rep(limiares_pw[2], n_points)), colour="black")

Cada micro-região representa uma folha. O espaço preditor 2-D está segmentado.

Agora,pondo uma figura 3D de um outro modelo aleatório como o de abaixo, percebemos também a estratificação, cada nível descreve a profundidade do ramal.

Vista superior da figura 3D:

Outro detalhe importante sobre a divisão do espaço, trabalhando-se com AD, é o que não acontece, como abaixo:


Como construir a árvore?

– Ideia Básica:

  1. Escolha o melhor preditor \(A\) e o seu melhor limiar de decisão para raiz da árvore.
  2. Separe o trainset \(S\) e, subsets \({S_1, S_2, ..., S_k}\), onde cada subset \(S_i\) contém amostras de igual valor para a condição imposta.
  3. Recursivamente, aplique o algoritmo para cada novo subset \(S_i\) até que todos os nós-terminais contenham a mesma classe.

Como escolher o melhor preditor feature no nó da árvore?

  1. Taxa do erro? -> Não converge bem, não é sensitiva ao crescimento da árvore.

  2. Índice Gini -> Medida de impureza do nó.

\[G({s_i}) = \sum_{k=1}^{K}{\hat{p}_{{s_i}k}(1-\hat{p}_{{s_i}k})}\]

  1. Entropia -> Quantidade de desordem, e pelo conceito da teoria de informação, a quantidade de bits necessário para guardar a variabilidade da informação.

\[E({s_i}) = -\sum_{k=1}^K{\hat{p}_{{s_i}k}\log{{\hat{p}}_{{s_i}k}}}\]


O Comportamento das funções em relação a distribuição das classes dentro do nó:

f_gini <- function(p){ p*(1-p) + (1-p)*(1-(1-p)) }
f_entr <- function(p){ ifelse(p%in%c(0,1), 0, 
                              - (p*log(p, base=2) + (1-p)*log((1-p), base=2)))}
ps <- seq(0, 1, length.out=100)
y_gini <- sapply(ps, f_gini)
y_entr <- sapply(ps, f_entr)
ggplot(tibble(probs=ps)) +
        geom_line(aes(x=probs, y=y_gini, colour="Gini")) +
        geom_line(aes(x=probs, y=y_entr, colour="Entropia")) +
        theme_bw()

 

Exemplo da escolha do critério de decisão usando Entropia.

Para simplificação do caso, continuamos somente no espaço 2-D dos preditores Petal Length e Petal Width.

1 - Medição de entropia no Nó Raiz.

O espaço Preditor original é mostrado abaixo, no caso \(S_1\), a raiz da árvore.

S1 <- train %>%  select(Petal.Length, Petal.Width, Species)
ggplot(S1, aes(x=Petal.Length, Petal.Width)) + 
        geom_point(aes(colour=Species)) +
        theme_bw()

Para calcular a entropia, precisamos somente da probabilidade de cada classe.

\[E({s_i}) = -\sum_{k=1}^K{\hat{p}_{{s_i}k}\log{{\hat{p}}_{{s_i}k}}}\]

S1 %>% group_by(Species) %>% 
        summarise(quantidade=n()) %>%
        mutate(prob=quantidade/sum(quantidade)) %>% 
        mutate(prob=round(prob, 3))

Computando a somatória do nó:

E_S1 <- - (0.339*log(0.339, base=2) + 0.339*log(0.339, base=2) + 0.321*log(0.321, base=2)) 
print(E_S1)
[1] 1.584349

 

2 - Critério para divisão:

Para decidir em quais dos pontos de decisão ocorrerá a divisão, usa-se o conceito de Ganho de Informação, que é a diferença de entropia entre os nós-filhos e o nó-pai.

\[\Delta{E} = p(S_{1})E(S_{1}) - \Big[p(S_{11})E(S_{11}) + p(S_{12})E(S_{12})\Big]\]

No nosso caso temos duas variáveis contínuas. Para cada atributo, são testados todos os valores contínuos do domínio daquela variável. O limiar que obter o maior valor de Ganho, é o selecionado.

fs_entropy <- function(S){
        if( nrow(S)==0){
                return( 0)
        }
        
        list_p <- S %>% 
                group_by(Species) %>% 
                summarise(quantidade=n()) %>%                   
                mutate(prob=quantidade/sum(quantidade)) %>% 
                .$prob
        
        list_p <- list_p[list_p > 0 | list_p < 1]
        entropia <- list_p %>% 
                        sapply(X=., FUN=function(p){ -p*log(p, base=2) }) %>%
                        sum()
        
        return(entropia)
}
delta_E <- tibble(attr=character(), thrs=numeric(), gain=numeric())
E_S1 <- fs_entropy(S1)
for( A in colnames(S1)[1:2]){
        range <- S1 %>% 
                select(eval(parse(text=A))) %>% 
                range()
        range_seq <- seq(range[1], range[2], 0.01)
        
        for( i in range_seq){
                S11 <- S1 %>% filter(get(A, pos=.) >= i)
                S12 <- S1 %>% filter(!get(A, pos=.) >= i)
                
                E_S11 <- fs_entropy(S11)
                E_S12 <- fs_entropy(S12)
                
                dE <- E_S1 - (1/nrow(S1))*(nrow(S11)*E_S11 + nrow(S12)*E_S12)        
                
                delta_E <- rbind.data.frame(delta_E, tibble(A, i, dE))
        
        }
        
        
}
ggplot(delta_E, aes(x=i, y=dE)) + 
        geom_line(aes(colour=A)) +
        facet_wrap(~A, nrow=1, scales="free_x") +
        theme_bw()

Aqui há um empate entre os dois atributos que antigem o mesmo o valor máximo de ganho. Em petal.length, o valor máximo se repete em uma faixa do domínio.

delta_E %>% filter(dE==max(dE)) %>%  filter(A=="Petal.Length") %>%  select(i) %>%  range()
[1] 1.91 3.00

O valor médio dessa faixa é exatamente o valor de corte escolhido na nossa primeira árvore. (O número aparente no diagrama árvore é arrendondado e por isso não bate exatamente.)

(1.91+3)/2
[1] 2.455

 

3 - Repetir o passo 1 e 2.

Replicar o processo de divisão com todos os novos nós-filhos gerados.

 


Podagem da Árvore e Overfitting

\[\sum_{m=1}^{|T|}\sum_{x_i\in{S_m}}(y_i - \hat{y}_{R_m})^2 + \alpha|T|\]

Após a árvore completamente modelada, existe uma tendência do algoritmo super ajustar os limites de decisão ao conjunto de treinamento, o algoritmo acaba aprendendo informações particulares do conjunto que são aleatoriedades da informação, e não necessariamente se repetirão para o conjunto de teste.

Para a podagem, adiciona-se um regulador \(\alpha\) que penaliza cada vez que o comprimento da árvore \(|T|\) cresça. A função converge, por exemplo, no momento que o ganho da divisão do nó não compensa mais o fator de punição.

tree.fit.pr <- prune(tree.fit, cp=0.1)
fancyRpartPlot(tree.fit.pr, sub="")

 


Comparando predição entre a árvore inteira e a podada.

Os dois primeiros números são a acertividade sobre o conjunto de treinamento, o primeiro valor é o da árvore inteira e o segundo a da podada, como esperado a da árvore intera se sobressai em performance, possuindo mais profundidade que segmente todas nuances do conjunto.

train.pred.1 <- predict(tree.fit, train, type="class")
## acertividade no trainset
mean(train.pred.1==train$Species) %>% round(3) %>% `*`(., 100)
train.pred.2 <- predict(tree.fit.pr, train, type="class")
## acertividade no trainset
mean(train.pred.2==train$Species) %>% round(3) %>% `*`(., 100)

 

Agora no conjunto de teste, a performance de ambas são equivalentes A árvore podada, de estrutura menos complexa, consegue atender igualmente predições para as amostras novas.

test.pred.1 <- predict(tree.fit, test, type="class")
## acertividade no testset
mean(test.pred.1==test$Species) %>% round(3) %>% `*`(., 100)
test.pred.2 <- predict(tree.fit.pr, test, type="class")
## acertividade no testset
mean(test.pred.2==test$Species) %>% round(3) %>% `*`(., 100)

 


Elencamentos

Construções de modelos bem mais poderosos usando árvores.

Bagging

Boosting

Random Forest

 


O Lado A e B do modelos de Árvore de Decisão

Prós

  • Boa interpretabilidade.
  • Funciona bem para todos os tipos de dados (caractere, fator, númerico, booleano).
  • Insensível a outliers.
  • Fácil de implementar.

Contras

  • Não performa bem para limites lineares ou suaves.
  • Tendência a overfitting (segue demasiado o ruído)
  • Não competitvo aos melhores algortimos de aprendizado supervisionado. Contudo com os métodos de elencamento, é extremamente poderoso, mas perde a interpretabilidade.

 

LS0tCnRpdGxlOiAiw4Fydm9yZXMgZGUgRGVjaXPDo28iCm91dHB1dDoKICBodG1sX25vdGVib29rOiBkZWZhdWx0CiAgaHRtbF9kb2N1bWVudDogZGVmYXVsdAptYXRoamF4OiBsb2NhbAotLS0KCioqKgojIyBPIFByb2JsZW1hCgpFc3NlIG5vdGVib29rIGludHJvZHV6IGNvbmNlaXRvcyBkbyBhbGdvcml0bW8gZGUgKirDgXJ2b3JlIGRlIERlY2lzw6NvKiogKEFEKSwgcGFyYSBpbHVzdHJhw6fDtWVzIGRvIGZhdG8sIHVzYXJlaSBvIGRhdGFzZXQgKklyaXMqLgoKYGBge3IsIG1lc3NhZ2U9RiwgZWNobz1ULCByZXN1bHRzPUZ9CiMgZXN0YWJlbGVjZW5kbyBvIGFtYmllbnRlCnN1cHByZXNzTWVzc2FnZXMoewogICAgICAgIGxpYnJhcnkodGlkeXZlcnNlKQogICAgICAgIGxpYnJhcnkobWFncml0dHIpCiAgICAgICAgbGlicmFyeShrbml0cikKICAgICAgICBsaWJyYXJ5KEdHYWxseSkKICAgICAgICBsaWJyYXJ5KHJwYXJ0KQogICAgICAgIGxpYnJhcnkocmF0dGxlKQogICAgICAgIGxpYnJhcnkocnBhcnQudXRpbHMpCiAgICAgICAgfSkgIAoKc2V0d2QoIn4vRHJvcGJveC9rYWdnbGUvaXJpcy1zcGVjaWVzLyIpICAKb3B0c19jaHVuayRzZXQoY2FjaGU9VFJVRSkgIAoKZGF0YShpcmlzKQppcmlzICU8PiUgIGFzX3RpYmJsZSgpCmBgYAoKTyBkYXRhc2V0IMONcmlzIGNvbnTDqW0gbWVkaWRhcyBkZSBjb21wcmltZW50byBlIGxhcmd1cmEgZGEgcMOpdGFsYSBlIGRhIHPDqXBhbGEgZGUgdHLDqnMgZXNww6ljaWVzIGRlIMOtcmlzOiAgIAoKKipWZXJzaWNvbG9yKioKPGRpdiBzdHlsZT0id2lkdGg6MzAwcHg7IGhlaWdodD0yMDBweCI+CiFbXSgvaG9tZS9yYWZhZWwvRHJvcGJveC9rYWdnbGUvaXJpcy1zcGVjaWVzL3BpY3MvaXJpcy12ZXJzaWNvbG9yLmpwZykKPC9kaXY+CiZuYnNwOwoKKipTZXRvc2EqKgo8ZGl2IHN0eWxlPSJ3aWR0aDozMDBweDsgaGVpZ2h0PTIwMHB4Ij4KIVtdKC9ob21lL3JhZmFlbC9Ecm9wYm94L2thZ2dsZS9pcmlzLXNwZWNpZXMvcGljcy9pcmlzLXNldG9zYS5qcGcpCjwvZGl2PgombmJzcDsKCioqVmlyZ8OtbmljYSoqCjxkaXYgc3R5bGU9IndpZHRoOjMwMHB4OyBoZWlnaHQ9MjAwcHgiPgohW10oL2hvbWUvcmFmYWVsL0Ryb3Bib3gva2FnZ2xlL2lyaXMtc3BlY2llcy9waWNzL2lyaXMtdmlyZ2luaWNhLmpwZykKPC9kaXY+CiZuYnNwOwoKKipFc3RydXR1cmEgZGEgZmxvcjoqKgo8ZGl2IHN0eWxlPSJ3aWR0aDozMDBweDsgaGVpZ2h0PTIwMHB4Ij4KIVtdKC9ob21lL3JhZmFlbC9Ecm9wYm94L2thZ2dsZS9pcmlzLXNwZWNpZXMvcGljcy9tb3Jmb2xvZ2lhLWRhLWZsb3IuanBnKQo8L2Rpdj4KKioqCgpPIGRhdGFzZXQgY29udMOpbSAxNTAgYW1vc3RyYXMsIDUwIGRlIGNhZGEgZXNww6ljaWUuIAoKYGBge3J9CmlyaXMgJT4lICBoZWFkKCkgJT4lIHByaW50KCkKYGBgCgoqKioKIyMgQSBtaXNzw6NvCgpDb25oZWNlciBvIGFsZ29yaXRtbyBkZSDDgXJ2b3JlIGRlIERlY2lzw6NvIGUgY3JpYXIgdW0gbW9kZWxvIHBvc3PDrXZlbCBkZSBwcmV2ZXIgYSBlc3DDqWNpZSBkZSDDrXJpcyBhIHBhcnRpciBkYXMgbWVkaWRhcyBkYSBww6l0YWxhIGUgc8OpcGFsYS4KCkFudGVzIGRhIG1vZGVsYWdlbSBlIGFuw6FsaXNlIGVtIGdlcmFsLCBvIHByaW1laXJvIHBhc3NvIMOpIGRpdmlkaXIgbyBjb25qdW50byBlbSBkYWRvcyBkZSB0cmVpbmFtZW50byBlIGRlIHRlc3RlLiBQYXJhIG7Do28gY3JpYXJtb3MgIHVtICpiaWFzKiBxdWUgaW5mbHVlbmNpZSBuYXMgcHJlZGnDp8O1ZXMgZmVpdGFzIHNvYnJlIG8gY29uanVudG8gZGUgdGVzdGUuCgpgYGB7cn0Kc2V0LnNlZWQoNjU0KQp0cmFpbl9pZHggPC0gc2FtcGxlKG5yb3coaXJpcyksIC43NSpucm93KGlyaXMpKQp0cmFpbiA8LSBpcmlzICU+JSBzbGljZSh0cmFpbl9pZHgpCnRlc3QgPC0gaXJpcyAlPiUgc2xpY2UoLXRyYWluX2lkeCkKYGBgCgpObyBkYXRhc2V0IGNvbnN0YW0gNCBwcmVkaXRvcmVzLCDDqSBpbnRlcmVzc2FudGUgY2hlY2FyIG8gbsOtdmVsIGRlIGNvcnJlbGHDp8OjbyBkZWxlcywgZSBvdSBzZXBhcmHDp8OjbyBubyBwbGFubyBxdWUgZGVsaW5laWUgYXMgY2xhc3NlcyBxdWUgcXVlcmVtb3MgY2xhc3NpZmljYXIuCgpgYGB7ciwgbWVzc2FnZT1GLCB3YXJuaW5nPUYsIHJlc3VsdHM9Rn0KdHJhaW4gJT4lCiAgICAgICAgZ2dwYWlycyhhZXMoY29sb3VyPVNwZWNpZXMpLCBjb2x1bW5zPTE6NCwgbG93ZXI9ImJsYW5rIiwgZGlhZz0iYmxhbmsiLCAKICAgICAgICAgICAgICAgICAgdXBwZXI9bGlzdChjb250aW51b3VzPSJwb2ludHMiKSkgKyB0aGVtZV9idygpIApgYGAKCgpBbGd1bWFzIHZhcmnDoXZlaXMgYXByZXNlbnRhbSB1bWEgY29ycmVsYcOnw6NvIGJlbSBmb3J0ZSwgY29tbyBgUGV0YWwuTGVuZ3RoYCBlIGBQZXRhbC5XaWR0aGAsIGUgYXMgcmVnacO1ZXMgZGUgdGFtYW5obyBkYXMgcMOpdGFsYXMgdGVtIHVtYSBhcHJlc2VudGFtIHVtYSBkaWZlcmVuY2lhw6fDo28gYmVtIGNsYXJhIGRhcyBjbGFzc2VzLgoKJm5ic3A7CgoKCioqKgojIyBBcHJlbmRpemFkbyBkZSBNw6FxdWluYQoKRGVudHJvIGRvIGVzcGHDp28gUHJlZGl0b3IgJFxMYXJnZXtYfSQgZW5jb250cmFyIGEgbWVsaG9yIHNlcGFyYcOnw6NvIGRlIHN1Yi1lc3Bhw6dvcyBxdWUgZGVzaWduZW0gY2FkYSBjbGFzc2UuCgoKJCQgXExhcmdle1xtYXRoY2Fse0Z9fSA6IFggXHJpZ2h0YXJyb3cgWSAkJAoKKioqCiMjIMOBcnZvcmUgZGUgRGVjaXPDo28KCi0gTcOpdG9kbyBkZSBjbGFzc2lmaWNhw6fDo28gZSByZWdyZXNzw6NvIG7Do28tcGFyYW3DqXRyaWNvIGUgbsOjby1saW5lYXIuCi0gRW52b2x2ZSBlc3RyYXRpZmljYcOnw6NvIGUgc2VnbWVudGHDp8OjbyBkbyBlc3Bhw6dvIGRlIHByZWRpdG9yZXMgZW0gdW0gbsO6bWVybyBkZSBwZXF1ZW5hcyByZWdpw7Vlcy4KCioqKgoKIyMjIERlZmluacOnw7VlcwogCk9saGFuZG8gdW0gZXhlbXBsbyBnZW7DqXJpY28gZGUgIEFEIHBhcmEgbyBjYXNvIMOtcmlzIG5hIGZpZ3VyYSBhYmFpeG8sIG5lc3NlIGV4ZW1wbG8gc8OzIGNvbnN0YW0gMiBwcmVkaXRvcmVzLgogCi0gQWJvcmRhZ2VtIFRvcC1Eb3duIC0+IGltYWdpbmEgYSDDoXJ2b3JlIGludmVydGlkYSwgbyBjdW1lIGRvIGdyYWZvIMOpIGEgKipSYWl6KiouCi0gT3MgbsOzcyBpbnRlcm5vcyBzw6NvICoqUmFtYWlzKiouCi0gT3MgbsOzcyB0ZXJtaW5haXMgc8OjbyAqKkZvbGhhcyoqLCBjYWRhIHF1YWwgZGVzaWduYSB1bWEgY2xhc3NlIGUgcmVwcmVzZW50YW0gbWljcm9zLXJlZ2nDtWVzIG9yaXVuZGFzIGRhIGRpdmlzw6NvIGRvIGVzcGHDp28gZGUgUHJlZGl0b3Jlcy4KCgpgYGB7cn0KdHJlZS5maXQgPC0gcnBhcnQoIlNwZWNpZXMgfiBQZXRhbC5MZW5ndGggKyBQZXRhbC5XaWR0aCIsIHRyYWluLCBjb250cm9sPXJwYXJ0LmNvbnRyb2woY3A9MCwgbWluYnVja2V0PTEpKQpmYW5jeVJwYXJ0UGxvdCh0cmVlLmZpdCwgc3ViPSIiKQpgYGAKCioqKgojIyMgUmVnacO1ZXMgZGUgZGVjaXPDo28KCmBgYHtyfQpsaW1pYXJlcyA8LSBycGFydC5zdWJydWxlcy50YWJsZSh0cmVlLmZpdCkgJT4lIAogICAgICAgICAgICAgICAgYXNfdGliYmxlKCkgJT4lCiAgICAgICAgICAgICAgICBzZWxlY3QoVmFyaWFibGUsIExlc3MpICU+JSAKICAgICAgICAgICAgICAgIGZpbHRlcighaXMubmEoTGVzcykpICU+JSAKICAgICAgICAgICAgICAgIG11dGF0ZShMZXNzPWFzLm51bWVyaWMoYXMuY2hhcmFjdGVyKExlc3MpKSkKICAgICAgICAgICAgICAgIApsaW1pYXJlc19wbCA8LSBsaW1pYXJlcyAlPiUgZmlsdGVyKFZhcmlhYmxlPT0iUGV0YWwuTGVuZ3RoIikgJT4lICAuJExlc3MgICAgICAgICAgIApsaW1pYXJlc19wdyA8LSBsaW1pYXJlcyAlPiUgZmlsdGVyKFZhcmlhYmxlPT0iUGV0YWwuV2lkdGgiKSAlPiUgIC4kTGVzcyAgICAgICAgICAgCgp4X2F4aXMgPC0gdHJhaW4kUGV0YWwuTGVuZ3RoICU+JSByYW5nZSgpCnlfYXhpcyA8LSB0cmFpbiRQZXRhbC5XaWR0aCAlPiUgcmFuZ2UoKQpuX3BvaW50cyA8LSB0cmFpbiAlPiUgbnJvdygpCiAgICAgICAgICAgIAp0cmFpbiAlPiUgZ2dwbG90KGFlcyh4PVBldGFsLkxlbmd0aCwgeT1QZXRhbC5XaWR0aCwgY29sb3VyPVNwZWNpZXMpKSArCiAgICAgICAgICAgIGdlb21fcG9pbnQoKSArIHRoZW1lX2J3KCkgKyBzY2FsZV94X2NvbnRpbnVvdXMoYnJlYWtzPXNlcSgxMCwxKSkgKwogICAgICAgICAgICBnZW9tX2xpbmUoYWVzKHg9cmVwKGxpbWlhcmVzX3BsWzFdLCBuX3BvaW50cyksIHk9c2VxKHlfYXhpc1sxXSwgeV9heGlzWzJdLCBsZW5ndGgub3V0PW5fcG9pbnRzKSksIGNvbG91cj0iYmxhY2siKSArIAogICAgICAgICAgICBnZW9tX2xpbmUoYWVzKHg9c2VxKGxpbWlhcmVzX3BsWzJdLCB4X2F4aXNbMl0sIGxlbmd0aC5vdXQ9bl9wb2ludHMpLCB5PXJlcChsaW1pYXJlc19wd1sxXSwgbl9wb2ludHMpKSwgY29sb3VyPSJibGFjayIpICsKICAgICAgICAgICAgZ2VvbV9saW5lKGFlcyh4PXJlcChsaW1pYXJlc19wbFsyXSwgbl9wb2ludHMpLCB5PXNlcSh5X2F4aXNbMV0sIHlfYXhpc1syXSwgbGVuZ3RoLm91dD1uX3BvaW50cykpLCBjb2xvdXI9ImJsYWNrIikgKwogICAgICAgICAgICBnZW9tX2xpbmUoYWVzKHg9c2VxKGxpbWlhcmVzX3BsWzJdLCB4X2F4aXNbMl0sIGxlbmd0aC5vdXQ9bl9wb2ludHMpLCB5PXJlcChsaW1pYXJlc19wd1sxXSwgbl9wb2ludHMpKSwgY29sb3VyPSJibGFjayIpICsKICAgICAgICAgICAgZ2VvbV9saW5lKGFlcyh4PXJlcChsaW1pYXJlc19wbFszXSwgbl9wb2ludHMpLCB5PXNlcSh5X2F4aXNbMV0sIGxpbWlhcmVzX3B3WzFdLCBsZW5ndGgub3V0PW5fcG9pbnRzKSksIGNvbG91cj0iYmxhY2siKSArCiAgICAgICAgICAgIGdlb21fbGluZShhZXMoeD1zZXEobGltaWFyZXNfcGxbM10sIHhfYXhpc1syXSwgbGVuZ3RoLm91dD1uX3BvaW50cyksIHk9cmVwKGxpbWlhcmVzX3B3WzJdLCBuX3BvaW50cykpLCBjb2xvdXI9ImJsYWNrIikKCmBgYAoKQ2FkYSBtaWNyby1yZWdpw6NvIHJlcHJlc2VudGEgdW1hIGZvbGhhLiBPIGVzcGHDp28gcHJlZGl0b3IgMi1EIGVzdMOhIHNlZ21lbnRhZG8uIAoKQWdvcmEscG9uZG8gdW1hIGZpZ3VyYSAzRCBkZSB1bSBvdXRybyBtb2RlbG8gYWxlYXTDs3JpbyBjb21vIG8gZGUgYWJhaXhvLCBwZXJjZWJlbW9zIHRhbWLDqW0gYSBlc3RyYXRpZmljYcOnw6NvLCBjYWRhIG7DrXZlbCBkZXNjcmV2ZSBhIHByb2Z1bmRpZGFkZSBkbyByYW1hbC4gIAoKPGRpdiBzdHlsZT0id2lkdGg6MzAwcHg7IGhlaWdodD0yMDBweCI+CiFbXSgvaG9tZS9yYWZhZWwvRHJvcGJveC9rYWdnbGUvaXJpcy1zcGVjaWVzL3BpY3Mvc3RyYXRpZmljYXRpb24tM0QucG5nKQo8L2Rpdj4KClZpc3RhIHN1cGVyaW9yIGRhIGZpZ3VyYSAzRDoKPGRpdiBzdHlsZT0id2lkdGg6MzAwcHg7IGhlaWdodD0yMDBweCI+CiFbXSgvaG9tZS9yYWZhZWwvRHJvcGJveC9rYWdnbGUvaXJpcy1zcGVjaWVzL3BpY3Mvby1xdWUtYS1hcnZvcmUtZmF6LnBuZykKPC9kaXY+CgoKKk91dHJvIGRldGFsaGUgaW1wb3J0YW50ZSBzb2JyZSBhIGRpdmlzw6NvIGRvIGVzcGHDp28sIHRyYWJhbGhhbmRvLXNlIGNvbSBBRCwgw6kgbyBxdWUgbsOjbyBhY29udGVjZSwgY29tbyBhYmFpeG86KgoKPGRpdiBzdHlsZT0id2lkdGg6MzAwcHg7IGhlaWdodD0yMDBweCI+CiFbXSgvaG9tZS9yYWZhZWwvRHJvcGJveC9rYWdnbGUvaXJpcy1zcGVjaWVzL3BpY3Mvby1xdWUtYS1hcnZvcmUtTkFPLWZhei5wbmcpCjwvZGl2PgoKCgoqKioKIyMjIENvbW8gY29uc3RydWlyIGEgw6Fydm9yZT8KCioqLS0gSWRlaWEgQsOhc2ljYToqKgoKMS4gRXNjb2xoYSBvIG1lbGhvciBwcmVkaXRvciAkQSQgZSBvIHNldSBtZWxob3IgbGltaWFyIGRlIGRlY2lzw6NvIHBhcmEgcmFpeiBkYSDDoXJ2b3JlLgoyLiBTZXBhcmUgbyB0cmFpbnNldCAkUyQgZSwgc3Vic2V0cyAke1NfMSwgU18yLCAuLi4sIFNfa30kLCBvbmRlIGNhZGEgc3Vic2V0ICRTX2kkIGNvbnTDqW0gYW1vc3RyYXMgZGUgaWd1YWwgdmFsb3IgcGFyYSBhIGNvbmRpw6fDo28gaW1wb3N0YS4KMy4gUmVjdXJzaXZhbWVudGUsIGFwbGlxdWUgbyBhbGdvcml0bW8gcGFyYSBjYWRhIG5vdm8gc3Vic2V0ICRTX2kkIGF0w6kgcXVlIHRvZG9zIG9zIG7Ds3MtdGVybWluYWlzIGNvbnRlbmhhbSBhIG1lc21hIGNsYXNzZS4KCioqQ29tbyBlc2NvbGhlciBvIG1lbGhvciBwcmVkaXRvciAqZmVhdHVyZSogbm8gbsOzIGRhIMOhcnZvcmU/KioKCjEuIFRheGEgZG8gZXJybz8gLT4gTsOjbyBjb252ZXJnZSBiZW0sIG7Do28gw6kgc2Vuc2l0aXZhIGFvIGNyZXNjaW1lbnRvIGRhIMOhcnZvcmUuCgoyLiDDjW5kaWNlIEdpbmkgLT4gTWVkaWRhIGRlIGltcHVyZXphIGRvIG7Dsy4KCiQkRyh7c19pfSkgPSBcc3VtX3trPTF9XntLfXtcaGF0e3B9X3t7c19pfWt9KDEtXGhhdHtwfV97e3NfaX1rfSl9JCQKCjMuIEVudHJvcGlhIC0+IFF1YW50aWRhZGUgZGUgZGVzb3JkZW0sIGUgcGVsbyBjb25jZWl0byBkYSAqdGVvcmlhIGRlIGluZm9ybWHDp8OjbyosIGEgcXVhbnRpZGFkZSBkZSBiaXRzIG5lY2Vzc8OhcmlvIHBhcmEgZ3VhcmRhciBhIHZhcmlhYmlsaWRhZGUgZGEgaW5mb3JtYcOnw6NvLgoKJCRFKHtzX2l9KSA9IC1cc3VtX3trPTF9Xkt7XGhhdHtwfV97e3NfaX1rfVxsb2d7e1xoYXR7cH19X3t7c19pfWt9fX0kJAoKKioqCk8gQ29tcG9ydGFtZW50byBkYXMgZnVuw6fDtWVzIGVtIHJlbGHDp8OjbyBhIGRpc3RyaWJ1acOnw6NvIGRhcyBjbGFzc2VzIGRlbnRybyBkbyBuw7M6CmBgYHtyfQpmX2dpbmkgPC0gZnVuY3Rpb24ocCl7IHAqKDEtcCkgKyAoMS1wKSooMS0oMS1wKSkgfQpmX2VudHIgPC0gZnVuY3Rpb24ocCl7IGlmZWxzZShwJWluJWMoMCwxKSwgMCwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIC0gKHAqbG9nKHAsIGJhc2U9MikgKyAoMS1wKSpsb2coKDEtcCksIGJhc2U9MikpKX0KCnBzIDwtIHNlcSgwLCAxLCBsZW5ndGgub3V0PTEwMCkKeV9naW5pIDwtIHNhcHBseShwcywgZl9naW5pKQp5X2VudHIgPC0gc2FwcGx5KHBzLCBmX2VudHIpCgpnZ3Bsb3QodGliYmxlKHByb2JzPXBzKSkgKwogICAgICAgIGdlb21fbGluZShhZXMoeD1wcm9icywgeT15X2dpbmksIGNvbG91cj0iR2luaSIpKSArCiAgICAgICAgZ2VvbV9saW5lKGFlcyh4PXByb2JzLCB5PXlfZW50ciwgY29sb3VyPSJFbnRyb3BpYSIpKSArCiAgICAgICAgdGhlbWVfYncoKQoKYGBgCgombmJzcDsKCiMjIyMgKipFeGVtcGxvIGRhIGVzY29saGEgZG8gY3JpdMOpcmlvIGRlIGRlY2lzw6NvIHVzYW5kbyBFbnRyb3BpYS4qKgoKUGFyYSBzaW1wbGlmaWNhw6fDo28gZG8gY2FzbywgY29udGludWFtb3Mgc29tZW50ZSBubyBlc3Bhw6dvIDItRCBkb3MgcHJlZGl0b3JlcyBgUGV0YWwgTGVuZ3RoYCBlIGBQZXRhbCBXaWR0aGAuCgoKKioxIC0gTWVkacOnw6NvIGRlIGVudHJvcGlhIG5vIE7DsyBSYWl6LioqCgpPIGVzcGHDp28gUHJlZGl0b3Igb3JpZ2luYWwgw6kgbW9zdHJhZG8gYWJhaXhvLCBubyBjYXNvICRTXzEkLCBhIHJhaXogZGEgw6Fydm9yZS4KCmBgYHtyfQpTMSA8LSB0cmFpbiAlPiUgIHNlbGVjdChQZXRhbC5MZW5ndGgsIFBldGFsLldpZHRoLCBTcGVjaWVzKQoKZ2dwbG90KFMxLCBhZXMoeD1QZXRhbC5MZW5ndGgsIFBldGFsLldpZHRoKSkgKyAKICAgICAgICBnZW9tX3BvaW50KGFlcyhjb2xvdXI9U3BlY2llcykpICsKICAgICAgICB0aGVtZV9idygpCmBgYAoKClBhcmEgY2FsY3VsYXIgYSBlbnRyb3BpYSwgcHJlY2lzYW1vcyBzb21lbnRlIGRhIHByb2JhYmlsaWRhZGUgZGUgY2FkYSBjbGFzc2UuCgokJEUoe3NfaX0pID0gLVxzdW1fe2s9MX1eS3tcaGF0e3B9X3t7c19pfWt9XGxvZ3t7XGhhdHtwfX1fe3tzX2l9a319fSQkCgpgYGB7cn0KUzEgJT4lIGdyb3VwX2J5KFNwZWNpZXMpICU+JSAKICAgICAgICBzdW1tYXJpc2UocXVhbnRpZGFkZT1uKCkpICU+JQogICAgICAgIG11dGF0ZShwcm9iPXF1YW50aWRhZGUvc3VtKHF1YW50aWRhZGUpKSAlPiUgCiAgICAgICAgbXV0YXRlKHByb2I9cm91bmQocHJvYiwgMykpCmBgYAoKQ29tcHV0YW5kbyBhIHNvbWF0w7NyaWEgZG8gbsOzOgpgYGB7cn0KRV9TMSA8LSAtICgwLjMzOSpsb2coMC4zMzksIGJhc2U9MikgKyAwLjMzOSpsb2coMC4zMzksIGJhc2U9MikgKyAwLjMyMSpsb2coMC4zMjEsIGJhc2U9MikpIApwcmludChFX1MxKQpgYGAKCiZuYnNwOwoKCioqMiAtIENyaXTDqXJpbyBwYXJhIGRpdmlzw6NvOioqIAoKUGFyYSBkZWNpZGlyIGVtIHF1YWlzIGRvcyBwb250b3MgZGUgZGVjaXPDo28gb2NvcnJlcsOhIGEgZGl2aXPDo28sIHVzYS1zZSBvIGNvbmNlaXRvIGRlICoqR2FuaG8gZGUgSW5mb3JtYcOnw6NvKiosIHF1ZSDDqSBhIGRpZmVyZW7Dp2EgZGUgZW50cm9waWEgZW50cmUgb3MgbsOzcy1maWxob3MgZSBvIG7Dsy1wYWkuCgokJFxEZWx0YXtFfSA9IHAoU197MX0pRShTX3sxfSkgLSBcQmlnW3AoU197MTF9KUUoU197MTF9KSArIHAoU197MTJ9KUUoU197MTJ9KVxCaWddJCQKCk5vIG5vc3NvIGNhc28gdGVtb3MgZHVhcyB2YXJpw6F2ZWlzIGNvbnTDrW51YXMuIFBhcmEgY2FkYSBhdHJpYnV0bywgc8OjbyB0ZXN0YWRvcyB0b2RvcyBvcyB2YWxvcmVzIGNvbnTDrW51b3MgZG8gZG9tw61uaW8gZGFxdWVsYSB2YXJpw6F2ZWwuIE8gbGltaWFyIHF1ZSBvYnRlciBvIG1haW9yIHZhbG9yIGRlIEdhbmhvLCDDqSBvIHNlbGVjaW9uYWRvLgoKYGBge3J9CmZzX2VudHJvcHkgPC0gZnVuY3Rpb24oUyl7CiAgICAgICAgaWYoIG5yb3coUyk9PTApewogICAgICAgICAgICAgICAgcmV0dXJuKCAwKQogICAgICAgIH0KICAgICAgICAKICAgICAgICBsaXN0X3AgPC0gUyAlPiUgCiAgICAgICAgICAgICAgICBncm91cF9ieShTcGVjaWVzKSAlPiUgCiAgICAgICAgICAgICAgICBzdW1tYXJpc2UocXVhbnRpZGFkZT1uKCkpICU+JSAgICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgIG11dGF0ZShwcm9iPXF1YW50aWRhZGUvc3VtKHF1YW50aWRhZGUpKSAlPiUgCiAgICAgICAgICAgICAgICAuJHByb2IKICAgICAgICAKICAgICAgICBsaXN0X3AgPC0gbGlzdF9wW2xpc3RfcCA+IDAgfCBsaXN0X3AgPCAxXQogICAgICAgIGVudHJvcGlhIDwtIGxpc3RfcCAlPiUgCiAgICAgICAgICAgICAgICAgICAgICAgIHNhcHBseShYPS4sIEZVTj1mdW5jdGlvbihwKXsgLXAqbG9nKHAsIGJhc2U9MikgfSkgJT4lCiAgICAgICAgICAgICAgICAgICAgICAgIHN1bSgpCiAgICAgICAgCiAgICAgICAgcmV0dXJuKGVudHJvcGlhKQp9CgoKZGVsdGFfRSA8LSB0aWJibGUoYXR0cj1jaGFyYWN0ZXIoKSwgdGhycz1udW1lcmljKCksIGdhaW49bnVtZXJpYygpKQpFX1MxIDwtIGZzX2VudHJvcHkoUzEpCmZvciggQSBpbiBjb2xuYW1lcyhTMSlbMToyXSl7CiAgICAgICAgcmFuZ2UgPC0gUzEgJT4lIAogICAgICAgICAgICAgICAgc2VsZWN0KGV2YWwocGFyc2UodGV4dD1BKSkpICU+JSAKICAgICAgICAgICAgICAgIHJhbmdlKCkKICAgICAgICByYW5nZV9zZXEgPC0gc2VxKHJhbmdlWzFdLCByYW5nZVsyXSwgMC4wMSkKICAgICAgICAKICAgICAgICBmb3IoIGkgaW4gcmFuZ2Vfc2VxKXsKICAgICAgICAgICAgICAgIFMxMSA8LSBTMSAlPiUgZmlsdGVyKGdldChBLCBwb3M9LikgPj0gaSkKICAgICAgICAgICAgICAgIFMxMiA8LSBTMSAlPiUgZmlsdGVyKCFnZXQoQSwgcG9zPS4pID49IGkpCiAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgIEVfUzExIDwtIGZzX2VudHJvcHkoUzExKQogICAgICAgICAgICAgICAgRV9TMTIgPC0gZnNfZW50cm9weShTMTIpCiAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgIGRFIDwtIEVfUzEgLSAoMS9ucm93KFMxKSkqKG5yb3coUzExKSpFX1MxMSArIG5yb3coUzEyKSpFX1MxMikgICAgICAgIAogICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICBkZWx0YV9FIDwtIHJiaW5kLmRhdGEuZnJhbWUoZGVsdGFfRSwgdGliYmxlKEEsIGksIGRFKSkKICAgICAgICAKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgCn0KCmdncGxvdChkZWx0YV9FLCBhZXMoeD1pLCB5PWRFKSkgKyAKICAgICAgICBnZW9tX2xpbmUoYWVzKGNvbG91cj1BKSkgKwogICAgICAgIGZhY2V0X3dyYXAofkEsIG5yb3c9MSwgc2NhbGVzPSJmcmVlX3giKSArCiAgICAgICAgdGhlbWVfYncoKQoKYGBgCgoKQXF1aSBow6EgdW0gZW1wYXRlIGVudHJlIG9zIGRvaXMgYXRyaWJ1dG9zIHF1ZSBhbnRpZ2VtIG8gbWVzbW8gbyB2YWxvciBtw6F4aW1vIGRlIGdhbmhvLiAgRW0gKnBldGFsLmxlbmd0aCosIG8gdmFsb3IgbcOheGltbyBzZSByZXBldGUgZW0gdW1hIGZhaXhhIGRvIGRvbcOtbmlvLgoKYGBge3J9CmRlbHRhX0UgJT4lIGZpbHRlcihkRT09bWF4KGRFKSkgJT4lICBmaWx0ZXIoQT09IlBldGFsLkxlbmd0aCIpICU+JSAgc2VsZWN0KGkpICU+JSAgcmFuZ2UoKQpgYGAKCk8gdmFsb3IgbcOpZGlvIGRlc3NhIGZhaXhhIMOpIGV4YXRhbWVudGUgbyB2YWxvciBkZSBjb3J0ZSBlc2NvbGhpZG8gbmEgbm9zc2EgcHJpbWVpcmEgw6Fydm9yZS4gKCpPIG7Dum1lcm8gYXBhcmVudGUgbm8gZGlhZ3JhbWEgw6Fydm9yZSDDqSBhcnJlbmRvbmRhZG8gZSBwb3IgaXNzbyBuw6NvIGJhdGUgZXhhdGFtZW50ZS4qKQoKYGBge3J9CigxLjkxKzMpLzIKYGBgCgombmJzcDsKCioqMyAtIFJlcGV0aXIgbyBwYXNzbyAxIGUgMi4qKgoKUmVwbGljYXIgbyBwcm9jZXNzbyBkZSBkaXZpc8OjbyBjb20gdG9kb3Mgb3Mgbm92b3MgbsOzcy1maWxob3MgZ2VyYWRvcy4KCiZuYnNwOwoKKioqCiMjIyBQb2RhZ2VtIGRhIMOBcnZvcmUgZSBPdmVyZml0dGluZwoKPGRpdiBzdHlsZT0id2lkdGg6MzAwcHg7IGhlaWdodD0yMDBweCI+CjxwIGFsaWduPSJjZW50ZXIiPgohW10oLi9waWNzL3RyZWUtcHJ1bmluZy1ndWlkZS5qcGcpCjwvcD4KPC9kaXY+CgoKJCRcc3VtX3ttPTF9Xnt8VHx9XHN1bV97eF9pXGlue1NfbX19KHlfaSAtIFxoYXR7eX1fe1JfbX0pXjIgKyBcYWxwaGF8VHwkJAoKQXDDs3MgYSDDoXJ2b3JlIGNvbXBsZXRhbWVudGUgbW9kZWxhZGEsIGV4aXN0ZSB1bWEgdGVuZMOqbmNpYSBkbyBhbGdvcml0bW8gc3VwZXIgYWp1c3RhciBvcyBsaW1pdGVzIGRlIGRlY2lzw6NvIGFvIGNvbmp1bnRvIGRlIHRyZWluYW1lbnRvLCBvIGFsZ29yaXRtbyBhY2FiYSBhcHJlbmRlbmRvIGluZm9ybWHDp8O1ZXMgcGFydGljdWxhcmVzIGRvIGNvbmp1bnRvIHF1ZSBzw6NvIGFsZWF0b3JpZWRhZGVzIGRhIGluZm9ybWHDp8OjbywgZSBuw6NvIG5lY2Vzc2FyaWFtZW50ZSBzZSByZXBldGlyw6NvIHBhcmEgbyBjb25qdW50byBkZSB0ZXN0ZS4KClBhcmEgYSBwb2RhZ2VtLCBhZGljaW9uYS1zZSB1bSByZWd1bGFkb3IgJFxhbHBoYSQgcXVlIHBlbmFsaXphIGNhZGEgdmV6IHF1ZSBvIGNvbXByaW1lbnRvIGRhIMOhcnZvcmUgJHxUfCQgY3Jlc8OnYS4gQSBmdW7Dp8OjbyBjb252ZXJnZSwgcG9yIGV4ZW1wbG8sIG5vIG1vbWVudG8gcXVlIG8gZ2FuaG8gZGEgZGl2aXPDo28gZG8gbsOzIG7Do28gY29tcGVuc2EgbWFpcyBvIGZhdG9yIGRlIHB1bmnDp8Ojby4gCgpgYGB7cn0KdHJlZS5maXQucHIgPC0gcHJ1bmUodHJlZS5maXQsIGNwPTAuMSkKZmFuY3lScGFydFBsb3QodHJlZS5maXQucHIsIHN1Yj0iIikKYGBgCgombmJzcDsKCioqKgojIyMgQ29tcGFyYW5kbyBwcmVkacOnw6NvIGVudHJlIGEgw6Fydm9yZSBpbnRlaXJhIGUgYSBwb2RhZGEuCgpPcyBkb2lzIHByaW1laXJvcyBuw7ptZXJvcyBzw6NvIGEgYWNlcnRpdmlkYWRlIHNvYnJlIG8gY29uanVudG8gZGUgdHJlaW5hbWVudG8sIG8gcHJpbWVpcm8gdmFsb3Igw6kgbyBkYSDDoXJ2b3JlIGludGVpcmEgZSBvIHNlZ3VuZG8gYSBkYSBwb2RhZGEsIGNvbW8gZXNwZXJhZG8gYSBkYSDDoXJ2b3JlIGludGVyYSBzZSBzb2JyZXNzYWkgZW0gcGVyZm9ybWFuY2UsIHBvc3N1aW5kbyBtYWlzIHByb2Z1bmRpZGFkZSBxdWUgc2VnbWVudGUgdG9kYXMgbnVhbmNlcyBkbyBjb25qdW50by4gCgpgYGB7cn0KdHJhaW4ucHJlZC4xIDwtIHByZWRpY3QodHJlZS5maXQsIHRyYWluLCB0eXBlPSJjbGFzcyIpCiMjIGFjZXJ0aXZpZGFkZSBubyB0cmFpbnNldAptZWFuKHRyYWluLnByZWQuMT09dHJhaW4kU3BlY2llcykgJT4lIHJvdW5kKDMpICU+JSBgKmAoLiwgMTAwKQpgYGAKCmBgYHtyfQp0cmFpbi5wcmVkLjIgPC0gcHJlZGljdCh0cmVlLmZpdC5wciwgdHJhaW4sIHR5cGU9ImNsYXNzIikKIyMgYWNlcnRpdmlkYWRlIG5vIHRyYWluc2V0Cm1lYW4odHJhaW4ucHJlZC4yPT10cmFpbiRTcGVjaWVzKSAlPiUgcm91bmQoMykgJT4lIGAqYCguLCAxMDApCmBgYAoKJm5ic3A7CgpBZ29yYSBubyBjb25qdW50byBkZSB0ZXN0ZSwgYSBwZXJmb3JtYW5jZSBkZSBhbWJhcyBzw6NvIGVxdWl2YWxlbnRlcyBBIMOhcnZvcmUgcG9kYWRhLCBkZSBlc3RydXR1cmEgbWVub3MgY29tcGxleGEsIGNvbnNlZ3VlIGF0ZW5kZXIgaWd1YWxtZW50ZSBwcmVkacOnw7VlcyBwYXJhIGFzIGFtb3N0cmFzIG5vdmFzLgoKCmBgYHtyfQp0ZXN0LnByZWQuMSA8LSBwcmVkaWN0KHRyZWUuZml0LCB0ZXN0LCB0eXBlPSJjbGFzcyIpCiMjIGFjZXJ0aXZpZGFkZSBubyB0ZXN0c2V0Cm1lYW4odGVzdC5wcmVkLjE9PXRlc3QkU3BlY2llcykgJT4lIHJvdW5kKDMpICU+JSBgKmAoLiwgMTAwKQpgYGAKCgpgYGB7cn0KdGVzdC5wcmVkLjIgPC0gcHJlZGljdCh0cmVlLmZpdC5wciwgdGVzdCwgdHlwZT0iY2xhc3MiKQojIyBhY2VydGl2aWRhZGUgbm8gdGVzdHNldAptZWFuKHRlc3QucHJlZC4yPT10ZXN0JFNwZWNpZXMpICU+JSByb3VuZCgzKSAlPiUgYCpgKC4sIDEwMCkKCmBgYAoKJm5ic3A7CgoqKioKIyMgRWxlbmNhbWVudG9zCgo+IENvbnN0cnXDp8O1ZXMgZGUgbW9kZWxvcyBiZW0gbWFpcyBwb2Rlcm9zb3MgdXNhbmRvIMOhcnZvcmVzLgoKKipCYWdnaW5nKioKCi0gQm9vdHN0cmFwIGUgY29tYmluYcOnw6NvIHBhcmFsZWxhLgoKKipCb29zdGluZyoqCgotIENvbWJpbmHDp8OjbyBzZXJpYWwgZGFzIMOhcnZvcmVzLgoKKipSYW5kb20gRm9yZXN0KioKCi0gQ29tYmluYcOnw6NvIHBhcmFsZWxhIGRhcyDDoXJ2b3JlcyAoICpub3JtYWxtZW50ZSBjb20gY2VudGVuYXMqICkgZSB0cnVxdWVzIGRlIGRlY29ycmVsYcOnw6NvIGVudHJlIGFzIMOhcnZvcmVzLgoKCiZuYnNwOwoKKioqCiMjIE8gTGFkbyBBIGUgQiBkbyBtb2RlbG9zIGRlIMOBcnZvcmUgZGUgRGVjaXPDo28KCiMjIyBQcsOzcwoKLSBCb2EgaW50ZXJwcmV0YWJpbGlkYWRlLgotIEZ1bmNpb25hIGJlbSBwYXJhIHRvZG9zIG9zIHRpcG9zIGRlIGRhZG9zIChjYXJhY3RlcmUsIGZhdG9yLCBuw7ptZXJpY28sIGJvb2xlYW5vKS4KLSBJbnNlbnPDrXZlbCBhIG91dGxpZXJzLgotIEbDoWNpbCBkZSBpbXBsZW1lbnRhci4KCiMjIyBDb250cmFzCgotIE7Do28gcGVyZm9ybWEgYmVtIHBhcmEgbGltaXRlcyBsaW5lYXJlcyBvdSBzdWF2ZXMuCi0gVGVuZMOqbmNpYSBhIG92ZXJmaXR0aW5nIChzZWd1ZSBkZW1hc2lhZG8gbyAqcnXDrWRvKikKLSBOw6NvIGNvbXBldGl0dm8gYW9zIG1lbGhvcmVzIGFsZ29ydGltb3MgZGUgYXByZW5kaXphZG8gc3VwZXJ2aXNpb25hZG8uIENvbnR1ZG8gY29tIG9zIG3DqXRvZG9zIGRlIGVsZW5jYW1lbnRvLCDDqSBleHRyZW1hbWVudGUgcG9kZXJvc28sIG1hcyBwZXJkZSBhIGludGVycHJldGFiaWxpZGFkZS4KCiZuYnNwOwo=